class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

}

/**
 * 19. 删除链表的倒数第 N 个结点
 * https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/?envType=study-plan-v2&envId=top-100-liked
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode r1 = reserve(head);//翻转链表
        //找到要删除的前一个节点
        ListNode prev = r1;
        if(n == 1) {
            //把头节点删除了
            return reserve(prev.next);
        }
        while(n-2 > 0) {
            prev = prev.next;
            n--;
        }

        ListNode cur = prev.next;//要删除的节点

        prev.next = cur.next;
        cur.next = null;

        return reserve(r1);
    }

    public ListNode reserve(ListNode head) {
        ListNode newHead = new ListNode();
        while(head != null) {
            ListNode next1 = newHead.next;//真正的头结点
            ListNode next2 = head.next;//下一次要遍历的节点
            newHead.next = head;
            head.next = next1;
            head = next2;
        }
        return newHead.next;
    }
}